Simulated Quantum Annealing (SQA) is a Markov Chain Monte-Carlo algorithmthat samples the equilibrium thermal state of a Quantum Annealing (QA)Hamiltonian. In addition to simulating quantum systems, SQA has also beenproposed as another physics-inspired classical algorithm for combinatorialoptimization, alongside classical simulated annealing. However, in many casesit remains an open challenge to determine the performance of both QA and SQA.One piece of evidence for the strength of QA over classical simulated annealingcomes from an example by Farhi, Goldstone and Gutmann . There a bit-symmetriccost function with a thin, high energy barrier was designed to show anexponential seperation between classical simulated annealing, for which thermalfluctuations take exponential time to climb the barrier, and quantum annealingwhich passes through the barrier and reaches the global minimum in poly time,arguably by taking advantage of quantum tunneling. In this work we apply acomparison method to rigorously show that the Markov chain underlying SQAefficiently samples the target distribution and finds the global minimum ofthis spike cost function in polynomial time. Our work provides evidence for thegrowing consensus that SQA inherits at least some of the advantages oftunneling in QA, and so QA is unlikely to achieve exponential speedups overclassical computing solely by the use of quantum tunneling. Since we analyzeonly a particular model this evidence is not decisive. However, techniquesapplied here---including warm starts from the adiabatic path and the use of thequantum ground state probability distribution to understand the stationarydistribution of SQA---may be valuable for future studies of the performance ofSQA on cost functions for which QA is efficient.
展开▼
